#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;

//1047.删除字符串中的所有相邻重复元素
string removeDuplicates(string s){
    string ret;

    //遍历原始字符串，将字符存放到另一个字符串中，如果当前字符和结果字符串中的最后一个相同，就删除
    //不相同就存放
    for(auto ch : s){
        if(ret.size()||ch==ret.back()){
            ret.pop_back();
        }
        else{
            ret += ch;
        }
    }
    return ret;
}

//844.比较含有退格的字符串
bool backspaceCompare(string s, string t){
    string ret1;
    string ret2;

    for(auto ch : s){
        if(ch=='#'){
            if(!ret1.empty()){
                ret1.pop_back();
            }
        }
        else{
            ret1 += ch;
        }
    }
    for(auto ch : t){
        if(ch=='#'){
            if(!ret2.empty()){
                ret2.pop_back();
            }
        }
        else{
            ret2 += ch;
        }
    }

    return ret1 == ret2;
}

//227.基本计算器2
int calculate(string s){
    //创建一个数组存放字符数字
    vector<int> nums;
    //设置一个字符变量用来记录字符符号
    char op = '+';

    for (int i = 0; i < s.size();){
        //如果当前字符是字符，跳过
        if(s[i]==' '){
            i++;
        }
        //如果当前字符是符号，修改op
        else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'){
            op = s[i++];
        }

        //如果当前字符是数字，往后遍历获取整个数字
        else{
            int tmp = s[i] - '0';
            while(++i&&s[i]>='0'&&s[i]<='9'){
                tmp = tmp * 10 + (s[i] - '0');
            }

            //获取整个数字后，判断当前符号
            if(op=='+'){
                nums.push_back(tmp);
            }
            if(op=='-'){
                nums.push_back(-tmp);
            }
            if(op=='*'){
                nums.back() *= tmp;
            }
            if(op=='/'){
                nums.back() /= tmp;
            }
        }
    }

    //遍历整个数组，将所有值相加
    int ret=0;
    for(auto num : nums){
        ret += num;
    }

    return ret;
}

//394.字符串解码
string decodeString(string s){
    //创建一个字符串栈，同时先存放一个空字符串，防止空栈时取出栈顶导致越界访问
    stack<string> sstrs;
    sstrs.push("");
    //创建一个数字栈，存放数字
    stack<int> snums;

    //遍历原始字符串
    for (int i = 0; i < s.size(); ){
        //如果遇到数字，就将该数字存放到数字栈中
        if(s[i]>='0'&&s[i]<='9'){
            int n = s[i] - '0';
            while(++i&&i<s.size()&&s[i]>='0'&&s[i]<='9'){
                n = n * 10 + (s[i] - '0');
            }
            snums.push(n);
        }

        //如果遇到'['，就取出后面的整个字符串，存放到字符串栈中
        if(s[i]=='['){
            string tmp;
            while(++i&&i<s.size()&&s[i]>='a'&&s[i]<='z'){
                tmp += s[i];
            }
            sstrs.push(tmp);
        }

        //如果遇到']'，就取出两个栈的栈顶元素，获取对应的字符串放到字符串栈的栈顶元素后面
        if(s[i]==']'){
            int count = snums.top();
            snums.pop();
            string tmp = sstrs.top();
            sstrs.pop();

            string cur;
            while(count--){
                cur += tmp;
            }

            sstrs.top() += cur;
            i++;
        }

        //如果遇到字符，就取出后面的整个字符串，存放到字符串栈的栈顶元素后面
        if(s[i]>='a'&&s[i]<='z'){
            string tmp;
            tmp += s[i];
            while(++i&&i<s.size()&&s[i]>='a'&&s[i]<='z'){
                tmp += s[i];
            }
            sstrs.top() += tmp;
        }
    }

    //最后返回字符串栈栈顶元素即可
    return sstrs.top();
}

//946.验证栈序列
bool validateStackSequences(vector<int>& pushed, vector<int>& popped){
    //创建一个栈
    stack<int> st;

    //遍历两个数组
    for (int i = 0, j = 0; i < pushed.size() && j < popped.size();){
        //如果入栈数组和出栈数组当前元素不同，将入栈元素存放到栈中
        if(pushed[i]!=popped[j]){
            st.push(pushed[i++]);
        }

        //如果相等，就出栈
        else{
            //两个下标都后移，相当于入栈再出栈
            i++;
            j++;

            //再循环判断后移后，出栈数组当前元素和栈顶元素是否相同,相同就出栈，后移,满足条件就循环进行
            while(!st.empty()&&st.top()==popped[j]&&j<popped.size()){
                st.pop();
                j++;
            }
        }
    }

    return st.empty();
}
int main(){
    string ret=decodeString({"2[abc]3[cd]ef"});
    for(auto ch : ret){
        cout << ch;
    }
    return 0;
}